﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class MedianFinder
{
    //优先级，数字小的排在队列前面
    PriorityQueue<int, int> queMax;//小于中位数的放大根堆queMax.Enqueue(num, num);
    PriorityQueue<int, int> queMin;//大于中位数的放小根堆queMin.Enqueue(num, -num);
    //大根堆比小根堆多一个数字，大根堆的堆顶就是中位数
    public MedianFinder()
    {
        queMax=new PriorityQueue<int, int>();
        queMin=new PriorityQueue<int, int>();
    }
    //小于中位数的放大根堆
    public void AddNum(int num)
    {

        //第一个数字加入大根堆,小于中位数的也加入

        if(queMax.Count == 0|| num< queMax.Peek())
        {
            queMax.Enqueue(num, -num);
            //更新中位数,大根堆比小跟堆大2

            if (queMax.Count > queMin.Count + 1)
            {

                int top = queMax.Dequeue();

                queMin.Enqueue(top, top);
            }

        }
        else
        {

            queMin.Enqueue(num, num);
            if (queMax.Count < queMin.Count)
            {

                int top = queMin.Dequeue();

                queMax.Enqueue(top, -top);
            }
        }

       

       

    }

    public double FindMedian()
    {
      

        if(queMax.Count == queMin.Count)
        {
            int max = queMax.Peek();
            int min = queMin.Peek();
            return (min + max) * 0.5;

        }else
        {
            return queMax.Peek();//小根堆可能没有数据
        }



    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.AddNum(num);
 * double param_2 = obj.FindMedian();
 */